import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//层序遍历二
class Solution3 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
   List<List<Integer>> list=new ArrayList<>();//创建一个二维数组
        if(root==null){
            return list;
        }
        Queue<TreeNode> qu=new LinkedList<>();
        qu.offer(root);
        while(!qu.isEmpty()){
        int size=qu.size();
        List<Integer>list1=new ArrayList<>();
         while(size>0){
             TreeNode cur=qu.poll();
             size--;
             list1.add(cur.val);
             if(cur.left!=null){
                 qu.offer(cur.left);
             }
             if(cur.right!=null){
                 qu.offer(cur.right);
             }
         }
         list.add(list1);
    }
        return list;
}
    }